IT鐵人上一次講到了三種Hazard：
| 類型 | 原因 |
|---|---|
| Structural Hazard(結構危障) | 硬體資源不夠多，導致在同一時間內要執行的多個指令無法執行。 |
| Data Hazard(資料危障) | Pipeline中某一指令需要用到前面指令尚未產生的結果，也就是執行的指令所需的資料還無法獲得。 |
| Control Hazard(控制危障) | Branch的結果尚未產生時，後續的指令就已經進入Pipeline，如果決定要branch到別的位置便會發生錯誤。所以又稱為Branch Hazard。 |
其實都能透過暫停Pipeline來解決，意思是不要急著插入下一個指令，塞幾個空格進去，避開Hazard後再來好好執行原先要執行的指令，這個作法就稱為Stall。
因為Structural的解決方式很簡單，只要把Insturction Memory跟Data Memory分開即可，所以以下討論Data Hazard跟Control Hazard的解決方法。
Data Hazard可以用軟體跟硬體的方法解決，軟體的分為NOP跟重新排列，硬體則是使用Forwarding。
通常我們Stall的方法是插入NOP，就是No Operation，以Data Hazard來說，需要寫回Register指令的後面兩個指令都不能用到該寫回的Register，因為這時該Register還沒更新到最新的結果，所以我們插入NOP的方式就會像是...
對於這樣的指令，因為$2要寫回去才能交給其他指令只用，所以要插入兩個NOP對齊WB跟ID，這樣子前半Cycle可以存入，後半Cycle可以取得更新的資料，就可以避免NOP。
| c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8 | c9 | c10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| sub | IF | ID | EX | MEM | WB (前半Cycle更新) | |||||
| nop (stall) | IF | ID | EX | MEM | WB | |||||
| nop (stall) | IF | ID | EX | MEM | WB | |||||
| and | IF | ID (後半Cycle取得) | EX | MEM | WB | |||||
| add | IF | ID | EX | MEM | WB | |||||
| sw | IF | ID | EX | MEM | WB |
重排指令順序通常是在Compiler負責執行，也就是說在編譯程式的時候，它就要想辦法把程式重新排列以便避開Data Hazard。
因為只要隔開兩格即可避免Data Hazard，我們可以將底下移動後不影響結果的指令向上移動，就能夠填補那兩格NOP指令，以下提供一個範例：
| 編號 | 指令 | |||
|---|---|---|---|---|
| 0 | lw | $t2 | 4($t0) | |
| 1 | add | $t3 | $t1 | $t2 |
| 2 | sub | $t6 | $t6 | $t7 |
| 3 | lw | $t4 | 8($t0) | |
| 4 | add | $t5 | $t1 | $t4 |
| 5 | and | $t8 | $t8 | $t9 |
在這邊0和1會在t2發生Data Hazard、3和4會在t4發生Data Hazard。
所以要在不影響結果的狀況下調動順序，我們可以將3拿到0的後面，然後1放在2的後面，如此一來就能保證t2及t4的指令會和原本Data Hazard的指令有兩格的差距，即可避免Data Hazard。結果如下：
| 編號 | 指令 | |||
|---|---|---|---|---|
| 0 | lw | $t2 | 4($t0) | |
| 3 | lw | $t4 | 8($t0) | |
| 2 | sub | $t6 | $t6 | $t7 |
| 1 | add | $t3 | $t1 | $t2 |
| 4 | add | $t5 | $t1 | $t4 |
| 5 | and | $t8 | $t8 | $t9 |
看起來就像事先把t2跟t4的值先從Data Memory中讀出來，在後面沒有Hazard的地方做運算避開Hazard。
重新排列順序有時後會發生無可避免的狀況，通常這時候就會直接插入NOP了，不過交給Compiler執行也會稍微耗費時間，所以我們也可以從硬體著手。
Forwarding的概念是這樣的，我直接把運算完的結果送到下一個指令要讀取的Register的地方，比如說我運算後要把結果存入t2，而後面的指令正好要取t2的數值，那麼我直接把數值交給它即可。
底下有一個範例，像是前三行的R1，後面的指令都直接需要，所以我們就接線過去把數值傳給它。
不過因為實際硬體的接線情況比較麻煩，原本的Datapath又會接的更複雜，想了解的同學就自己搜尋一下吧~
以實際生活發生的事情就像是：我去圖書館借書，要還的時候正好有人要借同一本書，那我就直接跟管理員說然後把書交給它。如此一來就可以避免丟進還書箱、圖書館員分類放好、想要的人再去找書完成借書程序。
至於Control Hazard的解決方，前面提到Control Hazard是因為Branch導致有指令需要丟掉，其實只要插入3個NOP就能解決，因為這時候PC就會指到對的指令位址，Instruction Memory就會輸出正確的指令。
所以這樣解決就可以了。
如果不知道結果怎麼樣的話，那用猜的不就好了，沒錯！
既然最差的情況是要等3個NOP，猜錯的話也只是捨棄結果再來重新跑指令，但是如果猜對了就沒有任何stall，那我們還不如一開始就猜結果，猜對賺到，猜錯也不虧。
猜的方式這邊要介紹兩種，分別是1-bit跟2-bit。
在這邊用Finit State Machine(FSM)表示，不知道這是什麼的同學，這邊簡單介紹一下，圓圈的部份代表現在的狀態，箭頭代表遇到什麼情況要轉換到哪個State。
以下是1-bit Prediction Scheme的FSM：
概念上就是如果這次的結果是yes，下個結果我就猜是yes，反之同理。
以下是2-bit Prediction Scheme的FSM：
概念上就是如果發生了連續兩次的yes，那麼就相信下個結果也是yes。
如果我現在站在永遠yes的狀況，只出現了一次no，我仍然相信下次還是yes。
舉個例子：
假設我現在在深藍色的Predict taken的State，然後發生了下列順序的結果，T代表taken(答案為yes或是我猜測yes)，NT代表not taken(答案為no或是我猜測no)：
發生結果 2-bit猜測 是否match? |T|T|yes|
|T|T|yes|
|N|T|no|
|T|T|yes|
|N|T|no|
|N|T|no|
|N|N|yes|
|N|N|yes|
|T|N|no|
|T|N|no|
|N|T|no|
這樣子發生了11次猜測，只有5次猜對，答對率不到一半，雖然看起來很差，不過這是為了舉例做出的結跟，所以跟實際情況有出入。
如果是平常的for迴圈，1000次之後才會跳出去，那麼可能只有1~3次會答錯，這麼看起來答對率超過99%，是很棒的預測。
這邊主要要跟大家說可以用猜測的方式減少Control Hazard發生的機率，實際硬體接線也是很複雜，畢竟還要丟掉不要的指令以及通知Branch發生，這邊就不特別說明了。
| 上一篇 | 下一篇 |
|---|---|
| Hazard | 近水樓台先得月 |
這篇教了大家概念上怎麼解決Hazard，雖然沒有跟大家說明硬體的部份，不過杰哥認為知道一下概念就好了，辛苦大家看到這邊了~ 最近幾篇的內容都蠻硬的，相信不少同學都被嚇到了，繼續努力吧~
iThome鐵人賽
看影片追技術